public class Solution {
    //乘积最大子数组
    public int maxProduct(int[] nums) {
        int n = nums.length;
        // 以i位置为结尾，此时的最大子数组乘积
        int[] f = new int[n];
        // 以i位置为结尾，此时的最小子数组乘积
        int[] g = new int[n];
        f[0] = nums[0];
        g[0] = nums[0];
        for (int i = 1; i < n; i++) {
            f[i] = Math.max(nums[i], Math.max(f[i-1]*nums[i],g[i-1]*nums[i]));
            g[i] = Math.min(nums[i], Math.min(g[i-1]*nums[i],f[i-1]*nums[i]));
        }
        int ret = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            ret = Math.max(f[i],ret);
        }
        return ret;
    }
    
}
